class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def getLDepth(root):
    ldepth = 0
    while root:
        root = root.left
        ldepth += 1
    return ldepth

def getRDepth(root):
    rdepth = 0
    while root:
        root = root.right
        rdepth += 1
    return rdepth

class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        lDepth = getLDepth(root)
        rDepth = getRDepth(root)
        if lDepth==rDepth:
            return 2**lDepth-1

        begin = 0
        end = int('1' * (lDepth-1), base=2)
        while begin<end:
            mid = (begin+end)//2
            seq = [0] * (lDepth-1)
            tmp = mid
            for i in range(lDepth-1):
                seq[i] = tmp % 2
                tmp //= 2
            
            tmp = root
            seq.reverse()
            for s in seq:
                if s==0: tmp = tmp.left
                else: tmp = tmp.right
            
            if tmp:
                begin=mid+1
            else:
                end=mid
        
        return begin + 2**(lDepth-1) - 1

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(Solution().countNodes(root))